package wtx.geek;

import java.util.*;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.Future;

import com.google.common.base.Joiner;
import javafx.util.Pair;
import sun.plugin.dom.exception.InvalidStateException;

/**
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
 *
 * 示例 1:
 *
 * 输入: S = "ababcbacadefegdehijhklij"
 * 输出: [9,7,8]
 * 解释:
 * 划分结果为 "ababcbaca", "defegde", "hijhklij"。
 * 每个字母最多出现在一个片段中。
 * 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-labels
 */

public class Solution {
    static final class Pair {
        int left, right;
        Pair(int l, int r) {
            left = l;
            right = r;
        }
        int length() {
            return right - left + 1;
        }
        Pair mergeOther(final Pair p) {
            return new Pair(Math.min(this.left, p.left), Math.max(this.right, p.right));
        }
        @Override
        public int hashCode() {
           return left*503 + length();
        }
    }
    static public List<Integer> partitionLabels(String S) {
        List<Pair> charInverseLocation = new ArrayList<>(26);
        for (int i = 0; i < 26; ++i) {
            charInverseLocation.add(null);
        }
        Map<Integer, Pair> rangeSet = new HashMap<>();
        for (int i = 0; i < S.length(); ++i) {
            int c = S.charAt(i) - 'a';
            if (charInverseLocation.get(c) == null) {
                charInverseLocation.set(c, new Pair(i, i));
            } else {
                Pair p0 = charInverseLocation.get(c),
                        p1 = new Pair(i, i);
                charInverseLocation.set(c, p0.mergeOther(p1));
            }
        }
        for (int i = 0; i < charInverseLocation.size(); ++i) {
            Pair curPair = charInverseLocation.get(i);
            if (curPair != null && curPair.length() == 1) {
                rangeSet.put(curPair.hashCode(), curPair);
                charInverseLocation.set(i, null);
            }
        }
        for (int i = 0; i < charInverseLocation.size(); ++i) {
            Pair curPair = charInverseLocation.get(i);
            if (curPair == null) {continue;}

            if (rangeSet.isEmpty()) {
                rangeSet.put(curPair.hashCode(), curPair);
            } else {
                ArrayList<Integer> mergeRange = new ArrayList<>();
                for (int pi : rangeSet.keySet()) {
                    Pair p = rangeSet.get(pi);
                    if (!(p.right < curPair.left || p.left > curPair.right )){
                        curPair = curPair.mergeOther(p);
                        mergeRange.add(pi);
                    }
                }
                for (int p : mergeRange) {
                   rangeSet.remove(p);
                }
                rangeSet.put(curPair.hashCode(), curPair);
            }
        }
        ArrayList<Pair> rangeList = new ArrayList<>(rangeSet.values());
        Collections.sort(rangeList, Comparator.comparingInt(p0 -> p0.left));
        ArrayList<Integer> retList = new ArrayList<>();
        for (Pair p : rangeList) {
            retList.add(p.length());
        }
        return retList;
    }
    static String shortenCandidateKey(String candidateKey) {
        String[] seg = candidateKey.split("=");
        StringJoiner sj = new StringJoiner(",");
        for (int i = 1; i < seg.length; ++i) {
            String[] s2 = seg[i].split(":");
            sj.add(s2[0]);
        }
        return sj.toString();
    }
    public static void main(String[] args) {
//        String S = "ababcbacadefegdehijhklij";
        String S = "mifeeds:queue:type=news_new_category_ctr:ncategory=民生:ordering=ctr";
        System.out.println(shortenCandidateKey(S));
    }
}
